Originally Posted by
laserlight
That's because you're looking at too small an N. Consider N=16:
x^16 = x^8 * x^8
x^8 = x^4 * x^4
x^4 = x^2 * x^2
x^2 = x * x
Hence, you only need 4 multiplications to compute x^16, not 15 multiplications.
Um... no. If you expand that, you get... (are you really making me type this out?)
Code:
power(x, 16);
power(x, 8) * power(x, 8);
power(x, 4) * power(x, 4) * power(x, 4) * power(x, 4);
power(x, 2) * power(x, 2) * power(x, 2) * power(x, 2) * power(x, 2) * power(x, 2) * power(x, 2) * power(x, 2);
x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x;
There are no fewer multiplications than if done manually.